class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        vector<int> stk(n + 1, 0);
        int r = 0, ans = 0;
        for(int i = 0, cur; i < n; ++i)
        {
            while(r > 0 && heights[stk[r - 1]] >= heights[i])
            {
                cur = stk[--r];
                int left = r > 0 ? stk[r - 1] : -1;
                ans = max(ans, heights[cur] * (i - left - 1));
            }
            stk[r++] = i;
        }

        int cur, left;
        while(r > 0)
        {
            cur = stk[--r];
            left = r > 0 ? stk[r - 1] : -1;
            ans = max(ans, heights[cur] * (n - left - 1));
        }

        return ans;
    }
};
